package com.shine.demo.leetCode.leetCodeOld;

import java.util.Arrays;

/**
 *  合并两个有序数组
 *  给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 *
 * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 *
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，
 * 后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
 *
 */
public class Solution {
    public static void main(String[] args) {

        System.out.println(Arrays.toString( merge(new int[]{4,5,6,0,0,0},3,new int[]{1,2,3},3)));
    }

    public static int[] merge(int[] nums1, int m, int[] nums2, int n) {
        //定义一个位置变量
        int index = 0;
        for (int i = 0; i < n; i++) {
            //找到nums2元素插入nums1的位置
            while (nums2[i] >= nums1[index] && index <m+i ){
                index++;
            }
            //将nums1该位置及之后元素往后挪
            for (int j = m+i; j >index ; j--) {
                    nums1[j] = nums1[j-1];
            }
            //插入nums2的元素
            nums1[index] = nums2[i];
        }
        return nums1;
    }


}
